package tianhao.luo.algorithm;

/**
 * 插入排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/18  10:09
 */
public class InsertSort {
    private int[] array;

    public InsertSort(int[] array) {
        this.array = array;
    }

    /**
     * 1. 初始状态:假定数组第一位元素(是R[0])组成一个有序的表,后面位置的元素组成一个无序的表
     * 2. 从无序表中取出一个元素(是R[1]),用它和有序表的最大元素(R[0])进行比较;
     *    1. 如果大,就直接插入有序表的最大元素的后一位(R[1]);
     *    2. 如果小于,就从有序表的最大元素开始向前查找并将有序表中大的元素后移,直到找到能够大于有序表中元素的位置索引i+1(被大于的元素索引为i),在i+1位置插入元素。
     * 3. 无序表中取元素的索引后移，直到无序表中扫描完毕
     */
    public void sort() {
        /*无效的算法
        // 创建一个有序表
        int[] orderArray = new int[array.length];

        // 1.从无序表中取出第一位元素,将它放入有序表中
        orderArray[0] = array[0];

        for (int i = 1; i < array.length; i++) {
            // 2.从无序表中取出上一次取出的元素位置后一位的元素;从有序表中的起始位置开始做比较,找到介于有序表中相邻元素之间的左位置
            int index = 0;
            // 问题:
            // 1.无法判断大于当前元素的位置,array[i] < orderArray[j + 1]这种判断在后一位是0的情况下,不会生效
            // (array[i] < orderArray[j + 1] || orderArray[j + 1] == 0)这种判断在插入了0之后,造成插入数据在0元素之前了
            // 2.无法控制有序表中,为空的元素还是在进行后移操作,有大量的无效操作
            for (int j = 0; j < orderArray.length - 1; j++) {
                // 找到介于两者直间的位置
                if (array[i] >= orderArray[j] && (array[i] < orderArray[j + 1] || orderArray[j + 1] == 0)) {
                    // 实际上可以插入的位置是介于两者之间的位置,就是j+1
                    index = j+1;
                    break;
                }

            }
            // 将index索引位置开始,依次后移一位
            for (int j = orderArray.length - 1; j >index ; j--) {
                orderArray[j] = orderArray[j-1];
            }
            orderArray[index] = array[i];
        }
        array = orderArray;
        */

        /*推导过程
        // 第一轮 {101,34,119,1} ==>{34,101,119,1}
        // 定义待插入的数
        int insertVal = array[1];
        // 从待插入的数的上一位开始
        int insertIndex = 1-1;


        // 插入排序,保证每一次进行插入操作时,待插入元素的索引的上一个元素是到此索引为止最大的元素
        // 给insertVal找到插入的位置
        // 说明
        // 1.insertIndex >=0 保证在给insertVal找插入位置,不越界
        // 2.insertVal<array[insertIndex] 待插入的数,没有找到合适的位置
        // 3.将array[insertIndex]的元素后移一位
        while (insertIndex >=0 && insertVal<array[insertIndex]){
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
        }
        // 当退出while循环时,说明插入的位置已经找到,即array[insertIndex]<insertVal,需要放置在大于insertIndex后一位的位置,即insertIndex+1
        array[insertIndex+1] = insertVal;

        // 第二轮排序{34,101,119,1}===>{34,101,119,1}
        // 定义待插入的数
        insertVal = array[2];
        // 插入排序,保证每一次进行插入操作时,待插入元素的索引的上一个元素是到此索引为止最大的元素
        // 从待插入的数的上一位开始
        insertIndex = 2-1;


        // 插入排序,保证每一次进行插入操作时,待插入元素的索引的上一个元素是到此索引为止最大的元素
        // 给insertVal找到插入的位置
        // 说明
        // 1.insertIndex >=0 保证在给insertVal找插入位置,不越界
        // 2.insertVal<array[insertIndex] 待插入的数,没有找到合适的位置
        // 3.将array[insertIndex]的元素后移一位
        while (insertIndex >=0 && insertVal<array[insertIndex]){
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
        }
        // 当退出while循环时,说明插入的位置已经找到,即array[insertIndex]<insertVal,需要放置在大于insertIndex后一位的位置,即insertIndex+1
        array[insertIndex+1] = insertVal;


        // 第三轮排序{34,101,119,1}===>{1,34,101,119}
        // 定义待插入的数
        insertVal = array[3];
        // 插入排序,保证每一次进行插入操作时,待插入元素的索引的上一个元素是到此索引为止最大的元素
        // 从待插入的数的上一位开始
        insertIndex = 3-1;


        // 插入排序,保证每一次进行插入操作时,待插入元素的索引的上一个元素是到此索引为止最大的元素
        // 给insertVal找到插入的位置
        // 说明
        // 1.insertIndex >=0 保证在给insertVal找插入位置,不越界
        // 2.insertVal<array[insertIndex] 待插入的数,没有找到合适的位置
        // 3.将array[insertIndex]的元素后移一位
        while (insertIndex >=0 && insertVal<array[insertIndex]){
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
        }
        // 当退出while循环时,说明插入的位置已经找到,即array[insertIndex]<insertVal,需要放置在大于insertIndex后一位的位置,即insertIndex+1
        array[insertIndex+1] = insertVal;
        */

        // 外层循环控制的是取出的插入元素索引,是需要取到数组末尾的
        for (int i = 1; i < array.length; i++) {
            int insertVal = array[i];
            // 从待插入的数的上一位开始
            int insertIndex = i-1;


            // 插入排序,保证每一次进行插入操作时,待插入元素的索引的上一个元素是到此索引为止最大的元素
            // 给insertVal找到插入的位置
            // 说明
            // 1.insertIndex >=0 保证在给insertVal找插入位置,不越界
            // 2.insertVal<array[insertIndex] 待插入的数,没有找到合适的位置
            // 3.将array[insertIndex]的元素后移一位
            // 若需从大到小,则将条件改为insertVal>array[insertIndex]即可
            while (insertIndex >=0 && insertVal<array[insertIndex]){
                array[insertIndex+1] = array[insertIndex];
                insertIndex--;
            }
            // 当退出while循环时,说明插入的位置已经找到,即array[insertIndex]<insertVal,需要放置在大于insertIndex后一位的位置,即insertIndex+1
            // 插入位置就是当前位置,不需发生交换
            if (insertIndex +1 != i){
                array[insertIndex+1] = insertVal;
            }
        }
    }

    /**
     * 打印
     */
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}
